package com.formula.datastructure.exercise.string;

/**
 * @author Leon@spark2fire.cn
 * @date 2021/4/29
 */
public class KMP {

    /**
     * abcabg, 前缀子串为["a", "ab", "abc", "abca", "abcab"], 后缀子串为["bcabg", "cabg", "abg", "bg", "g"]
     * next数组中储存的是这个字符串前缀和后缀中相同字符串的最长长度。比如abcdefgabc，前缀和后缀相同的是abc，长度是3。
     * <p>
     * next[i]储存的是string中前i+1位字符串前缀和后缀的最长长度。如abadefg，next[2]存的是aba这个字符串前缀和后缀的最长长度。
     */
    private int[] next;

    public boolean matches(String content, String pattern) {
        return false;
    }

    private void calculateNext(String pattern) {
        next = new int[pattern.length()];
        for (int last = 0; last < next.length; last++) {
            int count = 0;
            int i = 0;
            int j = i + 1;
            while (i <= last / 2) {
                if (pattern.charAt(i) == pattern.charAt(j)) {
                    i++;
                    j++;
                } else {

                }
            }
        }
    }
}
